#include <bits/stdc++.h>
using namespace std;

/*
2327. 知道秘密的人数
已解答
中等
相关标签
premium lock icon
相关企业
提示
在第 1 天，有一个人发现了一个秘密。

给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。

给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 109 + 7 取余 后返回。

 

示例 1：

输入：n = 6, delay = 2, forget = 4
输出：5
解释：
第 1 天：假设第一个人叫 A 。（一个人知道秘密）
第 2 天：A 是唯一一个知道秘密的人。（一个人知道秘密）
第 3 天：A 把秘密分享给 B 。（两个人知道秘密）
第 4 天：A 把秘密分享给一个新的人 C 。（三个人知道秘密）
第 5 天：A 忘记了秘密，B 把秘密分享给一个新的人 D 。（三个人知道秘密）
第 6 天：B 把秘密分享给 E，C 把秘密分享给 F 。（五个人知道秘密）
示例 2：

输入：n = 4, delay = 1, forget = 3
输出：6
解释：
第 1 天：第一个知道秘密的人为 A 。（一个人知道秘密）
第 2 天：A 把秘密分享给 B 。（两个人知道秘密）
第 3 天：A 和 B 把秘密分享给 2 个新的人 C 和 D 。（四个人知道秘密）
第 4 天：A 忘记了秘密，B、C、D 分别分享给 3 个新的人。（六个人知道秘密）
 

提示：

2 <= n <= 1000
1 <= delay < forget <= n
*/

// 法一
class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        // 双端队列know：存储"知道秘密但尚未开始分享"的人群信息
        // 每个元素为pair(知道秘密的起始天数, 该批次的人数)
        deque<pair<int, int>> know;
        // 双端队列share：存储"正在分享秘密"的人群信息
        // 每个元素为pair(开始分享的起始天数, 该批次的人数)
        deque<pair<int, int>> share;
        
        // 初始状态：第1天有1人知道秘密，加入know队列
        know.emplace_back(1, 1);
        int know_cnt = 1;  // 当前知道秘密但未开始分享的总人数
        int share_cnt = 0; // 当前正在分享秘密的总人数
        
        // 从第2天开始处理到第n天
        for (int i = 2; i <= n; ++i) {
            // 检查是否有批次达到开始分享的时间（知道秘密后delay天）
            // 若know队列头部的批次在i-delay天知道秘密，今天刚好可以开始分享
            if (!know.empty() && know[0].first == i - delay) {
                // 从know队列移除该批次，更新计数
                know_cnt = (know_cnt - know[0].second + mod) % mod;
                // 将该批次加入share队列，更新分享人数
                share_cnt = (share_cnt + know[0].second) % mod;
                share.push_back(know[0]);
                know.pop_front();
            }
            
            // 检查是否有批次达到停止分享的时间（知道秘密后forget天）
            // 若share队列头部的批次在i-forget天开始分享，今天刚好忘记秘密，停止分享
            if (!share.empty() && share[0].first == i - forget) {
                // 从share队列移除该批次，更新分享人数
                share_cnt = (share_cnt - share[0].second + mod) % mod;
                share.pop_front();
            }
            
            // 若当前有正在分享的人，他们今天会各分享给1个新的人
            if (!share.empty()) {
                // 新增的知道秘密的人数等于当前分享人数（每人每天分享1个）
                know_cnt = (know_cnt + share_cnt) % mod;
                // 记录这批新人知道秘密的起始天数为i，人数为share_cnt
                know.emplace_back(i, share_cnt);
            }
        }
        
        // 最终知道秘密的人数 = 未开始分享的人 + 正在分享的人（均未忘记）
        return (know_cnt + share_cnt) % mod;
    }

private:
    static constexpr int mod = 1000000007; // 取模常数
};

// 法二
class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        const int MOD = 1e9 + 7;
        // dp[i]表示第i天新增知道秘密的人数
        vector<long long> dp(n + 1, 0);
        // sum[i]表示前i天新增人数的总和（前缀和）
        vector<long long> sum(n + 1, 0);

        // 第1天有1人知道秘密
        dp[1] = 1;
        sum[1] = 1;
        
        for (int i = 2; i <= n; ++i) {
            // 计算贡献区间的左边界：最早可能分享秘密的人所在的天数
            int left = max(1, i - forget + 1);
            // 计算贡献区间的右边界：最晚可能分享秘密的人所在的天数
            int right = i - delay;
            if (right >= left) dp[i] = (sum[right] - sum[left - 1] + MOD) % MOD; // 区间[left, right]的和即为第i天新增的人数    
            else   dp[i] = 0;               // 没有符合条件的人分享秘密，新增人数为0
            // 更新前缀和
            sum[i] = (sum[i - 1] + dp[i]) % MOD;
        }
        // 计算第n天结束时仍知道秘密的人数：所有未忘记秘密的人
        int left = max(1, n - forget + 1);
        long long result = (sum[n] - sum[left - 1] + MOD) % MOD;
        
        return (int)result;
    }
};